<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 打家劫舍II题：
         * 输入：nums = [1,2,3,1]
         * 输出：4
         * 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。
         * 偷窃到的最高金额 = 1 + 3 = 4 。 
         * 
         * 思路：区别：首位连接成环，首尾不能同时去打劫，
         * 
        */
        /* 
            时间：O(n) nums的长度-2
            空间：O(n) nums数组的长度
        */
        var rob = function(nums) {
            let len = nums.length
            if (len === 0) {
                return 0
            }
            if (len === 1) {
                return nums[0]
            }
            function robRange (start, end) {
                let dp = new Array(nums.length).fill(0)
                dp[start] = nums[start]
                dp[start + 1] = Math.max(nums[start], nums[start + 1])
                // 从start + 2开始
                for (let j = start + 2; j <= end; j++) {
                  dp[j] = Math.max(dp[j - 1], dp[j - 2] + nums[j])
                }
                return dp[end]
            }
            // 关键：转化为0->n-2和1->n-1
            let result1 = robRange(0, nums.length - 2)
            let result2 = robRange(1, nums.length - 1)
            return Math.max(result1, result2)
        };
        // console.log(rob([2, 1, 1, 2]));
        // console.log(rob([2, 7, 9, 3, 1]));
        console.log(rob([1, 3, 1, 3, 100]));
    </script>
</body>

</html>